# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
	# @param {ListNode} head
	# @return {ListNode}
	def sortList(self, head):
		size = 0
		h = head
		H = ListNode(None)
		H.next = head
		while h:
			h = h.next
			size += 1
		start = H

		self.__sort(H, size/2, size-size/2)
		return H.next

	def __sort(self, H, l_len, r_len):
		# do something?
		if l_len == 0 or r_len == 0:
			z = H
			for i in xrange(l_len + r_len):
				z = z.next
			return z
		leftEnd = self.__sort(H, l_len/2, l_len-l_len/2)

		self.__sort(leftEnd, r_len/2, r_len-r_len/2)
		
		h = H

		lp = h.next
		rp = lp
		for j in xrange(l_len):
			rp = rp.next
		tail = rp
		for t in xrange(r_len):
			tail = tail.next
		# H ... h,lp... ,rp... ,tail
		count_l = count_r = 0
		temp = h
		while count_l < l_len and count_r < r_len:
			if lp.val <= rp.val:
				temp.next = lp
				lp = lp.next
				count_l += 1
			else:
				temp.next = rp
				rp = rp.next
				count_r += 1
			temp = temp.next
		while count_l < l_len:
			temp.next = lp
			lp = lp.next
			count_l += 1
			temp = temp.next
		while count_r < r_len:
			temp.next = rp
			rp = rp.next
			count_r += 1
			temp = temp.next
		temp.next = tail
		return temp

if __name__ == '__main__':
	h = ListNode(10)
	it = h
	for i in [7,4,3,2,8,6,9,10,22]:
		it.next = ListNode(i)
		it = it.next
	so = Solution()
	x = so.sortList(h)
	z = []
	while x:
		z.append(x.val)
		x = x.next
	print z
